notebook.community

Edit and run 





In [1]:



    


import networkx as nx
import matplotlib.pyplot as plt
from collections import Counter
from custom import custom_funcs as cf
import warnings
warnings.filterwarnings('ignore')
from circos import CircosPlot


%load_ext autoreload
%autoreload 2
%matplotlib inline

Load Data

We will load the sociopatterns network data for this notebook. From the Konect website:

This network describes the face-to-face behavior of people during the exhibition INFECTIOUS: STAY AWAY in 2009 at the Science Gallery in Dublin. Nodes represent exhibition visitors; edges represent face-to-face contacts that were active for at least 20 seconds. Multiple edges between two nodes are possible and denote multiple contacts. The network contains the data from the day with the most interactions.





In [2]:



    


# Load the sociopatterns network data. 
G = cf.load_sociopatterns_network()

Hubs: How do we evaluate the importance of some individuals in a network?

Within a social network, there will be certain individuals which perform certain important functions. For example, there may be hyper-connected individuals who are connected to many, many more people. They would be of use in the spreading of information. Alternatively, if this were a disease contact network, identifying them would be useful in stopping the spread of diseases. How would one identify these people?

Approach 1: Neighbors

One way we could compute this is to find out the number of people an individual is conencted to. NetworkX let's us do this by giving us a G.neighbors(node) function.





In [26]:



    


# Let's find out the number of neighbors that individual #7 has.
len(G.neighbors(7))



    


















    
Out[26]:








7

Exercise

Can you create a ranked list of the importance of each individual, based on the number of neighbors they have?

Hint: One suggested output would be a list of tuples, where the first element in each tuple is the node ID (an integer number), and the second element is the number of neighbors that it has.

Hint: Python's sorted(iterable, key=lambda x:...., reverse=True) function may be of help here.





In [28]:



    


# Possible Answers:
# sorted(G.nodes(), key=lambda x:len(G.neighbors(x)), reverse=True)
sorted([(n, G.neighbors(n)) for n in G.nodes()], key=lambda x: len(x[1]), reverse=True)



    


















    
Out[28]:








[(51,
  [1,
   45,
   133,
   7,
   136,
   141,
   142,
   143,
   144,
   154,
   32,
   176,
   35,
   164,
   165,
   38,
   40,
   41,
   42,
   173,
   223,
   47,
   48,
   49,
   178,
   52,
   183,
   57,
   187,
   188,
   190,
   191,
   64,
   65,
   66,
   67,
   71,
   72,
   74,
   205,
   112,
   36,
   37,
   50,
   100,
   240,
   168,
   117,
   125,
   127]),
 (272,
  [385,
   263,
   264,
   285,
   290,
   291,
   294,
   297,
   305,
   306,
   307,
   312,
   314,
   188,
   318,
   319,
   321,
   324,
   228,
   327,
   328,
   331,
   333,
   336,
   338,
   339,
   340,
   341,
   345,
   346,
   347,
   348,
   351,
   354,
   355,
   356,
   230,
   358,
   357,
   359,
   365,
   369,
   371,
   373,
   376,
   377,
   379]),
 (195,
  [257,
   258,
   259,
   196,
   197,
   198,
   199,
   200,
   265,
   202,
   262,
   204,
   205,
   206,
   207,
   210,
   291,
   277,
   278,
   215,
   216,
   260,
   218,
   219,
   261,
   263,
   226,
   283,
   292,
   229,
   231,
   323,
   235,
   236,
   237,
   238,
   241,
   299,
   248,
   267,
   287,
   266,
   264]),
 (235,
  [257,
   258,
   195,
   259,
   197,
   262,
   199,
   264,
   201,
   266,
   270,
   173,
   147,
   260,
   207,
   265,
   221,
   261,
   288,
   225,
   226,
   227,
   291,
   229,
   294,
   231,
   232,
   233,
   234,
   263,
   237,
   238,
   239,
   240,
   241,
   244,
   292,
   247,
   313,
   314,
   287,
   299,
   296]),
 (161,
  [192,
   66,
   214,
   215,
   147,
   148,
   149,
   150,
   151,
   152,
   153,
   154,
   155,
   156,
   157,
   158,
   159,
   160,
   162,
   163,
   164,
   165,
   169,
   173,
   174,
   175,
   178,
   218,
   181,
   183,
   212,
   122,
   188,
   85]),
 (219,
  [194,
   195,
   196,
   197,
   198,
   199,
   200,
   201,
   202,
   204,
   205,
   206,
   207,
   210,
   148,
   213,
   215,
   218,
   156,
   222,
   229,
   240,
   227,
   165,
   230,
   231,
   232,
   236,
   238,
   175,
   176,
   241,
   183,
   251]),
 (265,
  [257,
   258,
   195,
   260,
   261,
   262,
   263,
   264,
   266,
   267,
   274,
   259,
   326,
   216,
   281,
   283,
   288,
   327,
   291,
   292,
   293,
   294,
   296,
   298,
   235,
   301,
   321,
   307,
   308,
   312,
   314,
   188,
   299,
   255]),
 (50,
  [1,
   2,
   133,
   51,
   136,
   31,
   74,
   75,
   142,
   143,
   144,
   174,
   175,
   165,
   32,
   176,
   37,
   168,
   169,
   171,
   172,
   173,
   46,
   47,
   48,
   177,
   178,
   179,
   117,
   58,
   123,
   188,
   126]),
 (181,
  [67,
   198,
   199,
   200,
   202,
   207,
   208,
   148,
   153,
   155,
   156,
   158,
   160,
   161,
   162,
   164,
   165,
   169,
   170,
   171,
   173,
   174,
   175,
   176,
   177,
   178,
   179,
   180,
   182,
   183,
   184,
   185,
   187]),
 (292,
  [257,
   258,
   259,
   260,
   263,
   264,
   265,
   267,
   268,
   270,
   195,
   281,
   282,
   283,
   284,
   285,
   287,
   288,
   291,
   324,
   293,
   294,
   295,
   296,
   297,
   298,
   235,
   300,
   301,
   307,
   312,
   314,
   299]),
 (122,
  [128,
   129,
   130,
   131,
   132,
   133,
   134,
   72,
   168,
   144,
   91,
   156,
   95,
   161,
   100,
   103,
   104,
   105,
   108,
   109,
   112,
   113,
   117,
   118,
   73,
   120,
   121,
   123,
   124,
   125,
   126,
   127]),
 (148,
  [149,
   150,
   151,
   152,
   153,
   154,
   155,
   156,
   157,
   158,
   159,
   160,
   161,
   162,
   219,
   164,
   165,
   169,
   170,
   171,
   173,
   174,
   175,
   177,
   178,
   179,
   117,
   182,
   183,
   188,
   181]),
 (288,
  [257,
   258,
   299,
   261,
   262,
   263,
   265,
   266,
   268,
   216,
   281,
   282,
   283,
   284,
   285,
   287,
   291,
   292,
   293,
   294,
   295,
   296,
   297,
   298,
   235,
   300,
   301,
   303,
   304,
   305,
   314]),
 (294,
  [258,
   259,
   260,
   261,
   265,
   266,
   267,
   270,
   272,
   280,
   281,
   282,
   283,
   284,
   285,
   287,
   288,
   291,
   292,
   293,
   295,
   296,
   297,
   298,
   235,
   300,
   301,
   302,
   249,
   314,
   299]),
 (188,
  [51,
   259,
   132,
   264,
   265,
   270,
   271,
   272,
   286,
   148,
   214,
   215,
   283,
   284,
   222,
   287,
   161,
   166,
   230,
   298,
   300,
   112,
   113,
   50,
   115,
   308,
   117,
   189,
   190,
   309]),
 (100,
  [66,
   133,
   134,
   95,
   84,
   85,
   90,
   91,
   93,
   94,
   37,
   96,
   97,
   101,
   102,
   103,
   104,
   105,
   106,
   108,
   109,
   110,
   111,
   51,
   116,
   120,
   122,
   38,
   42]),
 (299,
  [258,
   259,
   260,
   261,
   262,
   264,
   265,
   267,
   195,
   281,
   282,
   283,
   284,
   285,
   287,
   288,
   291,
   292,
   293,
   294,
   295,
   296,
   297,
   298,
   235,
   300,
   301,
   312,
   314]),
 (171,
  [179,
   134,
   148,
   149,
   214,
   218,
   223,
   224,
   228,
   165,
   113,
   169,
   170,
   172,
   173,
   174,
   175,
   112,
   177,
   50,
   115,
   181,
   238,
   233,
   184,
   212,
   58,
   117]),
 (199,
  [193,
   195,
   196,
   197,
   198,
   200,
   201,
   202,
   204,
   205,
   206,
   207,
   227,
   218,
   219,
   157,
   163,
   228,
   229,
   231,
   235,
   236,
   237,
   238,
   239,
   240,
   181,
   255]),
 (257,
  [258,
   195,
   260,
   261,
   262,
   263,
   264,
   265,
   266,
   267,
   259,
   216,
   281,
   282,
   314,
   287,
   288,
   291,
   292,
   295,
   296,
   297,
   235,
   300,
   312,
   249,
   250,
   252]),
 (264,
  [257,
   258,
   195,
   260,
   261,
   262,
   263,
   265,
   266,
   267,
   272,
   259,
   278,
   216,
   281,
   282,
   292,
   295,
   296,
   298,
   235,
   300,
   301,
   244,
   309,
   308,
   188,
   299]),
 (240,
  [197,
   198,
   199,
   200,
   201,
   202,
   206,
   216,
   219,
   223,
   224,
   225,
   227,
   229,
   231,
   232,
   233,
   234,
   235,
   236,
   237,
   238,
   239,
   241,
   51,
   244,
   246]),
 (261,
  [257,
   258,
   195,
   260,
   262,
   263,
   264,
   265,
   266,
   267,
   268,
   270,
   259,
   216,
   281,
   288,
   290,
   291,
   293,
   294,
   296,
   297,
   298,
   235,
   300,
   315,
   299]),
 (293,
  [259,
   260,
   261,
   262,
   265,
   266,
   280,
   281,
   282,
   283,
   284,
   285,
   287,
   288,
   291,
   292,
   294,
   295,
   296,
   297,
   298,
   299,
   300,
   301,
   305,
   309,
   314]),
 (297,
  [257,
   259,
   260,
   261,
   263,
   266,
   267,
   272,
   280,
   282,
   283,
   284,
   285,
   287,
   288,
   291,
   292,
   293,
   294,
   295,
   296,
   298,
   299,
   300,
   307,
   312,
   314]),
 (359,
  [385,
   329,
   272,
   337,
   339,
   340,
   345,
   346,
   347,
   348,
   351,
   352,
   353,
   354,
   355,
   356,
   357,
   358,
   362,
   363,
   364,
   365,
   369,
   374,
   376,
   379,
   380]),
 (42,
  [19,
   67,
   71,
   72,
   73,
   74,
   77,
   3,
   88,
   28,
   93,
   100,
   37,
   38,
   39,
   41,
   43,
   44,
   45,
   51,
   54,
   105,
   56,
   58,
   60,
   62]),
 (103,
  [128,
   86,
   87,
   89,
   90,
   91,
   93,
   94,
   95,
   96,
   97,
   99,
   100,
   101,
   102,
   104,
   105,
   106,
   107,
   108,
   109,
   110,
   111,
   113,
   122,
   123]),
 (112,
  [64,
   129,
   130,
   115,
   132,
   113,
   140,
   56,
   84,
   94,
   95,
   167,
   168,
   124,
   171,
   172,
   111,
   177,
   114,
   51,
   120,
   122,
   187,
   188,
   125,
   190]),
 (198,
  [193,
   195,
   196,
   197,
   199,
   200,
   201,
   202,
   204,
   205,
   206,
   207,
   163,
   219,
   222,
   227,
   231,
   232,
   236,
   237,
   238,
   239,
   240,
   241,
   181,
   248]),
 (230,
  [132,
   353,
   331,
   204,
   270,
   335,
   272,
   210,
   334,
   260,
   219,
   221,
   224,
   225,
   226,
   228,
   229,
   360,
   361,
   362,
   239,
   336,
   242,
   245,
   188,
   213]),
 (287,
  [257,
   195,
   260,
   263,
   281,
   282,
   283,
   284,
   285,
   288,
   291,
   292,
   293,
   294,
   295,
   296,
   297,
   298,
   235,
   300,
   301,
   304,
   247,
   314,
   188,
   299]),
 (291,
  [257,
   195,
   261,
   263,
   265,
   272,
   323,
   281,
   282,
   283,
   284,
   285,
   287,
   288,
   292,
   293,
   294,
   295,
   296,
   297,
   298,
   235,
   300,
   301,
   314,
   299]),
 (296,
  [257,
   259,
   261,
   264,
   265,
   266,
   281,
   282,
   283,
   284,
   285,
   287,
   288,
   291,
   292,
   293,
   294,
   295,
   297,
   298,
   235,
   300,
   301,
   312,
   314,
   299]),
 (95,
  [75,
   147,
   84,
   87,
   88,
   91,
   93,
   94,
   96,
   97,
   100,
   101,
   102,
   103,
   104,
   105,
   106,
   108,
   109,
   110,
   112,
   114,
   115,
   122,
   38]),
 (132,
  [130,
   131,
   133,
   134,
   135,
   140,
   58,
   222,
   246,
   228,
   230,
   168,
   124,
   112,
   113,
   115,
   117,
   118,
   121,
   122,
   123,
   188,
   189,
   190,
   127]),
 (197,
  [195,
   196,
   198,
   199,
   200,
   201,
   202,
   204,
   205,
   206,
   207,
   216,
   219,
   227,
   229,
   231,
   232,
   233,
   235,
   236,
   238,
   239,
   240,
   241,
   248]),
 (207,
  [194,
   195,
   196,
   197,
   198,
   199,
   200,
   201,
   202,
   204,
   205,
   206,
   214,
   219,
   226,
   165,
   166,
   231,
   232,
   233,
   235,
   238,
   239,
   241,
   181]),
 (229,
  [195,
   196,
   197,
   199,
   201,
   210,
   218,
   219,
   225,
   226,
   227,
   228,
   230,
   231,
   232,
   233,
   234,
   235,
   236,
   237,
   238,
   239,
   240,
   241,
   250]),
 (231,
  [195,
   196,
   197,
   198,
   199,
   200,
   204,
   206,
   207,
   212,
   219,
   226,
   227,
   229,
   232,
   233,
   234,
   235,
   236,
   237,
   238,
   239,
   240,
   241,
   244]),
 (259,
  [192,
   257,
   258,
   195,
   260,
   261,
   262,
   263,
   264,
   265,
   266,
   267,
   216,
   281,
   285,
   292,
   293,
   294,
   295,
   296,
   297,
   235,
   314,
   188,
   299]),
 (260,
  [257,
   258,
   195,
   261,
   262,
   263,
   264,
   265,
   266,
   267,
   294,
   259,
   277,
   216,
   299,
   282,
   283,
   285,
   287,
   292,
   293,
   230,
   295,
   297,
   235]),
 (298,
  [258,
   261,
   264,
   265,
   267,
   281,
   282,
   283,
   284,
   285,
   287,
   288,
   291,
   292,
   293,
   294,
   295,
   296,
   297,
   299,
   300,
   301,
   314,
   188,
   318]),
 (345,
  [385,
   386,
   387,
   388,
   391,
   394,
   272,
   339,
   340,
   341,
   346,
   347,
   348,
   351,
   352,
   400,
   354,
   355,
   356,
   357,
   358,
   359,
   364,
   365,
   374]),
 (117,
  [131,
   132,
   118,
   124,
   147,
   148,
   214,
   87,
   226,
   164,
   168,
   169,
   171,
   50,
   178,
   51,
   182,
   233,
   121,
   122,
   187,
   188,
   126,
   127]),
 (165,
  [207,
   146,
   148,
   149,
   151,
   152,
   153,
   154,
   155,
   156,
   157,
   158,
   161,
   162,
   219,
   164,
   171,
   173,
   174,
   177,
   50,
   51,
   181,
   183]),
 (183,
  [51,
   115,
   211,
   148,
   151,
   154,
   219,
   156,
   161,
   164,
   165,
   169,
   170,
   173,
   174,
   175,
   176,
   177,
   178,
   179,
   180,
   181,
   182,
   184]),
 (202,
  [192,
   193,
   195,
   196,
   197,
   198,
   199,
   200,
   201,
   204,
   205,
   206,
   207,
   209,
   211,
   213,
   215,
   219,
   163,
   232,
   237,
   238,
   240,
   181]),
 (237,
  [195,
   196,
   198,
   199,
   202,
   206,
   223,
   224,
   225,
   226,
   227,
   229,
   231,
   232,
   233,
   234,
   235,
   236,
   238,
   239,
   240,
   241,
   248,
   250]),
 (258,
  [257,
   195,
   260,
   261,
   262,
   263,
   264,
   265,
   266,
   267,
   268,
   259,
   216,
   281,
   282,
   283,
   284,
   288,
   292,
   294,
   298,
   235,
   314,
   299]),
 (281,
  [257,
   258,
   259,
   261,
   264,
   265,
   280,
   216,
   282,
   283,
   284,
   285,
   287,
   288,
   291,
   292,
   293,
   294,
   295,
   296,
   298,
   299,
   301,
   314]),
 (282,
  [257,
   258,
   260,
   262,
   264,
   267,
   281,
   283,
   284,
   285,
   287,
   288,
   291,
   292,
   293,
   294,
   295,
   296,
   297,
   298,
   299,
   300,
   301,
   314]),
 (283,
  [258,
   195,
   260,
   262,
   324,
   265,
   281,
   282,
   284,
   285,
   287,
   288,
   291,
   292,
   293,
   294,
   295,
   296,
   297,
   298,
   299,
   301,
   314,
   188]),
 (295,
  [257,
   259,
   260,
   262,
   264,
   279,
   281,
   282,
   283,
   284,
   285,
   287,
   288,
   291,
   292,
   293,
   294,
   296,
   297,
   298,
   299,
   301,
   302,
   314]),
 (74,
  [66,
   67,
   70,
   71,
   72,
   75,
   76,
   77,
   78,
   81,
   19,
   86,
   87,
   102,
   38,
   105,
   42,
   45,
   50,
   51,
   54,
   55,
   56]),
 (105,
  [71,
   74,
   147,
   88,
   91,
   93,
   94,
   95,
   96,
   97,
   99,
   100,
   101,
   102,
   103,
   104,
   106,
   43,
   109,
   110,
   113,
   122,
   42]),
 (113,
  [64,
   132,
   133,
   134,
   120,
   124,
   58,
   101,
   103,
   168,
   105,
   171,
   172,
   175,
   112,
   114,
   115,
   169,
   56,
   122,
   187,
   188,
   125]),
 (154,
  [193,
   51,
   148,
   149,
   150,
   151,
   152,
   153,
   155,
   156,
   157,
   158,
   159,
   160,
   161,
   162,
   164,
   165,
   169,
   175,
   177,
   179,
   183]),
 (177,
  [115,
   148,
   151,
   153,
   154,
   156,
   112,
   50,
   165,
   169,
   170,
   171,
   172,
   173,
   174,
   175,
   176,
   178,
   179,
   181,
   182,
   183,
   184]),
 (179,
  [148,
   154,
   156,
   50,
   232,
   169,
   170,
   171,
   173,
   174,
   175,
   176,
   177,
   178,
   180,
   181,
   182,
   183,
   185,
   251,
   253,
   254,
   255]),
 (206,
  [195,
   196,
   197,
   198,
   199,
   200,
   201,
   202,
   239,
   205,
   207,
   210,
   214,
   215,
   219,
   163,
   231,
   237,
   238,
   175,
   240,
   180,
   182]),
 (227,
  [196,
   197,
   198,
   199,
   204,
   208,
   209,
   211,
   219,
   225,
   226,
   228,
   229,
   231,
   232,
   233,
   235,
   236,
   237,
   238,
   239,
   240,
   241]),
 (232,
  [196,
   197,
   198,
   202,
   207,
   219,
   226,
   227,
   229,
   231,
   233,
   234,
   235,
   236,
   237,
   238,
   239,
   240,
   241,
   179,
   245,
   251,
   255]),
 (262,
  [257,
   258,
   195,
   260,
   261,
   263,
   264,
   265,
   266,
   267,
   259,
   216,
   299,
   282,
   283,
   284,
   288,
   293,
   295,
   235,
   300,
   301,
   314]),
 (284,
  [258,
   262,
   280,
   281,
   282,
   283,
   285,
   287,
   288,
   291,
   292,
   293,
   294,
   295,
   296,
   297,
   298,
   299,
   300,
   301,
   305,
   314,
   188]),
 (314,
  [257,
   258,
   259,
   262,
   265,
   272,
   281,
   282,
   283,
   284,
   287,
   288,
   291,
   292,
   293,
   294,
   295,
   296,
   297,
   298,
   235,
   309,
   299]),
 (93,
  [43,
   131,
   90,
   91,
   94,
   95,
   96,
   97,
   99,
   100,
   101,
   102,
   103,
   104,
   105,
   106,
   107,
   108,
   109,
   110,
   118,
   42]),
 (120,
  [128,
   129,
   130,
   133,
   134,
   140,
   141,
   163,
   100,
   166,
   168,
   109,
   112,
   113,
   118,
   121,
   122,
   123,
   124,
   125,
   126,
   127]),
 (164,
  [148,
   149,
   150,
   152,
   153,
   154,
   156,
   158,
   159,
   160,
   161,
   162,
   165,
   166,
   174,
   178,
   51,
   181,
   182,
   183,
   184,
   117]),
 (169,
  [148,
   154,
   157,
   161,
   113,
   170,
   171,
   172,
   173,
   174,
   175,
   176,
   177,
   50,
   179,
   180,
   117,
   182,
   183,
   184,
   185,
   181]),
 (173,
  [51,
   171,
   148,
   157,
   161,
   165,
   169,
   170,
   235,
   172,
   178,
   174,
   175,
   176,
   177,
   50,
   179,
   181,
   182,
   183,
   184,
   185]),
 (174,
  [148,
   157,
   224,
   161,
   50,
   164,
   165,
   166,
   169,
   170,
   171,
   173,
   175,
   176,
   177,
   178,
   179,
   181,
   182,
   183,
   184,
   185]),
 (196,
  [195,
   197,
   198,
   199,
   200,
   201,
   202,
   204,
   205,
   206,
   207,
   209,
   215,
   219,
   227,
   229,
   231,
   232,
   236,
   237,
   239,
   241]),
 (238,
  [195,
   197,
   198,
   199,
   202,
   206,
   207,
   235,
   219,
   225,
   226,
   227,
   229,
   231,
   232,
   233,
   234,
   171,
   236,
   237,
   239,
   240]),
 (239,
  [196,
   197,
   198,
   199,
   205,
   206,
   207,
   225,
   226,
   227,
   229,
   230,
   231,
   232,
   233,
   234,
   235,
   236,
   237,
   238,
   240,
   241]),
 (318,
  [384,
   386,
   389,
   328,
   329,
   272,
   341,
   346,
   353,
   315,
   380,
   298,
   371,
   308,
   376,
   377,
   378,
   379,
   316,
   381,
   382,
   383]),
 (91,
  [96,
   97,
   98,
   99,
   100,
   101,
   102,
   103,
   104,
   105,
   93,
   108,
   110,
   125,
   122,
   86,
   88,
   90,
   118,
   94,
   95]),
 (109,
  [96,
   97,
   99,
   100,
   101,
   38,
   103,
   104,
   105,
   106,
   107,
   108,
   110,
   111,
   93,
   120,
   122,
   95,
   90,
   94,
   133]),
 (118,
  [128,
   129,
   130,
   91,
   132,
   133,
   134,
   136,
   93,
   144,
   146,
   117,
   87,
   120,
   121,
   122,
   123,
   124,
   125,
   126,
   127]),
 (125,
  [128,
   129,
   130,
   91,
   133,
   214,
   144,
   112,
   113,
   146,
   51,
   56,
   118,
   215,
   120,
   121,
   122,
   123,
   124,
   126,
   127]),
 (156,
  [160,
   161,
   162,
   219,
   164,
   165,
   181,
   224,
   177,
   179,
   148,
   149,
   150,
   183,
   152,
   153,
   122,
   155,
   154,
   158,
   159]),
 (233,
  [225,
   226,
   227,
   229,
   231,
   200,
   236,
   171,
   172,
   237,
   238,
   207,
   240,
   232,
   117,
   235,
   197,
   239,
   247,
   248,
   223]),
 (263,
  [288,
   257,
   258,
   259,
   260,
   261,
   262,
   307,
   264,
   265,
   266,
   235,
   300,
   291,
   272,
   305,
   195,
   297,
   267,
   292,
   287]),
 (285,
  [288,
   259,
   260,
   293,
   294,
   295,
   296,
   297,
   298,
   299,
   300,
   301,
   272,
   291,
   309,
   281,
   292,
   282,
   283,
   284,
   287]),
 (87,
  [133,
   118,
   70,
   71,
   73,
   74,
   103,
   44,
   78,
   81,
   83,
   84,
   110,
   86,
   89,
   88,
   116,
   95,
   94,
   117]),
 (94,
  [96,
   97,
   75,
   100,
   101,
   102,
   103,
   104,
   105,
   107,
   108,
   109,
   110,
   112,
   146,
   99,
   87,
   91,
   93,
   95]),
 (124,
  [149,
   129,
   130,
   131,
   132,
   133,
   144,
   108,
   112,
   113,
   58,
   117,
   118,
   120,
   121,
   122,
   123,
   125,
   126,
   127]),
 (144,
  [58,
   129,
   50,
   51,
   168,
   137,
   138,
   140,
   141,
   143,
   88,
   146,
   147,
   84,
   118,
   56,
   121,
   122,
   124,
   125]),
 (175,
  [161,
   50,
   177,
   169,
   170,
   171,
   172,
   173,
   174,
   176,
   113,
   178,
   179,
   148,
   181,
   206,
   183,
   184,
   154,
   219]),
 (300,
  [288,
   257,
   291,
   292,
   261,
   262,
   263,
   264,
   188,
   298,
   299,
   296,
   293,
   294,
   297,
   279,
   282,
   284,
   285,
   287]),
 (301,
  [288,
   289,
   291,
   292,
   293,
   262,
   295,
   264,
   265,
   298,
   299,
   294,
   296,
   275,
   281,
   282,
   283,
   284,
   285,
   287]),
 (341,
  [368,
   354,
   355,
   329,
   382,
   331,
   372,
   367,
   272,
   339,
   340,
   350,
   342,
   343,
   344,
   345,
   379,
   349,
   318,
   377]),
 (356,
  [352,
   353,
   354,
   355,
   357,
   358,
   359,
   361,
   332,
   365,
   366,
   335,
   272,
   369,
   339,
   345,
   346,
   347,
   348,
   351]),
 (367,
  [353,
   386,
   388,
   392,
   361,
   363,
   396,
   366,
   335,
   336,
   408,
   400,
   339,
   340,
   341,
   406,
   407,
   344,
   378,
   349]),
 (389,
  [384,
   385,
   386,
   387,
   390,
   392,
   393,
   407,
   335,
   400,
   403,
   404,
   374,
   375,
   408,
   409,
   378,
   399,
   410,
   318]),
 (110,
  [64,
   97,
   131,
   100,
   101,
   102,
   103,
   104,
   105,
   106,
   107,
   140,
   109,
   99,
   87,
   91,
   93,
   94,
   95]),
 (121,
  [129,
   130,
   131,
   132,
   134,
   140,
   142,
   144,
   145,
   116,
   117,
   118,
   120,
   88,
   122,
   123,
   124,
   125,
   127]),
 (123,
  [128,
   129,
   131,
   132,
   134,
   103,
   160,
   140,
   50,
   146,
   99,
   118,
   120,
   121,
   122,
   124,
   125,
   126,
   127]),
 (126,
  [128,
   129,
   130,
   131,
   133,
   134,
   167,
   96,
   50,
   143,
   146,
   117,
   118,
   120,
   122,
   123,
   124,
   125,
   127]),
 (133,
  [128,
   129,
   100,
   134,
   102,
   168,
   109,
   113,
   50,
   51,
   118,
   87,
   120,
   132,
   122,
   124,
   125,
   126,
   127]),
 (149,
  [160,
   161,
   164,
   165,
   166,
   167,
   124,
   171,
   172,
   148,
   150,
   151,
   152,
   153,
   154,
   155,
   156,
   157,
   158]),
 (215,
  [161,
   163,
   196,
   195,
   220,
   202,
   172,
   211,
   206,
   208,
   147,
   244,
   214,
   217,
   218,
   219,
   188,
   125,
   191]),
 (335,
  [400,
   386,
   387,
   356,
   342,
   230,
   361,
   362,
   395,
   333,
   367,
   336,
   337,
   338,
   404,
   374,
   375,
   399,
   389]),
 (348,
  [352,
   368,
   354,
   355,
   356,
   357,
   358,
   359,
   328,
   361,
   364,
   365,
   272,
   371,
   340,
   345,
   346,
   347,
   351]),
 (44,
  [32, 75, 36, 37, 71, 41, 42, 43, 45, 78, 77, 92, 73, 87, 27, 28, 29, 69]),
 (146,
  [128,
   129,
   66,
   147,
   165,
   138,
   140,
   142,
   143,
   144,
   145,
   114,
   115,
   94,
   118,
   123,
   125,
   126]),
 (160,
  [161,
   162,
   123,
   164,
   85,
   181,
   148,
   149,
   150,
   151,
   152,
   153,
   154,
   155,
   156,
   157,
   158,
   159]),
 (176,
  [193,
   163,
   51,
   169,
   170,
   173,
   174,
   175,
   50,
   177,
   178,
   179,
   180,
   181,
   182,
   183,
   184,
   219]),
 (178,
  [161,
   164,
   51,
   170,
   173,
   174,
   175,
   176,
   177,
   50,
   179,
   148,
   117,
   183,
   184,
   180,
   185,
   181]),
 (200,
  [194,
   195,
   196,
   197,
   198,
   199,
   201,
   202,
   231,
   204,
   205,
   206,
   207,
   240,
   244,
   181,
   233,
   219]),
 (204,
  [230,
   194,
   195,
   196,
   197,
   198,
   199,
   200,
   201,
   202,
   231,
   205,
   207,
   227,
   151,
   228,
   219,
   247]),
 (378,
  [384,
   386,
   387,
   389,
   328,
   329,
   367,
   371,
   382,
   393,
   376,
   377,
   346,
   379,
   380,
   381,
   318,
   383]),
 (37, [33, 100, 38, 39, 40, 41, 42, 43, 44, 48, 49, 50, 51, 7, 71, 62, 65]),
 (41, [32, 37, 39, 92, 42, 43, 44, 45, 77, 51, 52, 54, 55, 57, 71, 27, 28]),
 (97,
  [96,
   99,
   100,
   101,
   71,
   104,
   105,
   106,
   103,
   108,
   109,
   110,
   90,
   91,
   93,
   94,
   95]),
 (104,
  [96,
   97,
   99,
   100,
   103,
   105,
   106,
   107,
   109,
   110,
   93,
   145,
   90,
   91,
   122,
   94,
   95]),
 (127,
  [128,
   129,
   130,
   131,
   132,
   133,
   51,
   115,
   117,
   118,
   120,
   121,
   122,
   123,
   124,
   125,
   126]),
 (129,
  [128,
   144,
   130,
   133,
   134,
   112,
   146,
   116,
   118,
   120,
   121,
   122,
   123,
   124,
   125,
   126,
   127]),
 (152,
  [160,
   161,
   162,
   164,
   165,
   66,
   148,
   149,
   150,
   151,
   153,
   154,
   155,
   156,
   157,
   158,
   159]),
 (153,
  [160,
   161,
   162,
   164,
   165,
   181,
   177,
   148,
   149,
   150,
   85,
   152,
   154,
   155,
   156,
   158,
   159]),
 (157,
  [160,
   161,
   162,
   165,
   199,
   169,
   170,
   173,
   174,
   148,
   149,
   151,
   152,
   154,
   155,
   158,
   159]),
 (158,
  [160,
   161,
   162,
   164,
   165,
   181,
   148,
   149,
   150,
   152,
   153,
   154,
   155,
   156,
   157,
   85,
   159]),
 (228,
  [224,
   225,
   226,
   227,
   132,
   229,
   230,
   199,
   171,
   204,
   321,
   272,
   343,
   331,
   319,
   190,
   223]),
 (236,
  [225,
   195,
   196,
   197,
   198,
   199,
   232,
   233,
   234,
   231,
   237,
   238,
   239,
   240,
   227,
   219,
   229]),
 (241,
  [225,
   226,
   195,
   196,
   229,
   198,
   231,
   232,
   201,
   235,
   239,
   237,
   207,
   240,
   227,
   219,
   197]),
 (244,
  [193,
   194,
   163,
   231,
   200,
   235,
   240,
   264,
   242,
   212,
   215,
   248,
   217,
   255,
   252,
   222,
   247]),
 (266,
  [288,
   257,
   258,
   259,
   260,
   261,
   262,
   263,
   264,
   265,
   235,
   294,
   296,
   195,
   297,
   267,
   293]),
 (267,
  [257,
   258,
   259,
   260,
   261,
   262,
   263,
   264,
   265,
   266,
   299,
   294,
   195,
   297,
   292,
   282,
   298]),
 (312,
  [193,
   323,
   292,
   325,
   257,
   296,
   265,
   299,
   304,
   272,
   305,
   306,
   307,
   308,
   309,
   310,
   297]),
 (340,
  [353,
   359,
   329,
   333,
   334,
   365,
   272,
   339,
   372,
   341,
   342,
   343,
   345,
   367,
   348,
   349,
   350]),
 (400,
  [409,
   385,
   386,
   387,
   389,
   404,
   397,
   335,
   401,
   372,
   373,
   375,
   408,
   345,
   399,
   367,
   410]),
 (12, [3, 36, 5, 6, 8, 9, 10, 11, 13, 14, 16, 17, 20, 23, 4, 26]),
 (16, [3, 33, 35, 36, 5, 8, 9, 10, 11, 12, 13, 14, 15, 17, 19, 23]),
 (71, [97, 37, 70, 72, 105, 42, 87, 44, 88, 51, 84, 85, 73, 41, 24, 74]),
 (102,
  [96, 100, 101, 103, 105, 106, 107, 108, 110, 93, 95, 90, 91, 74, 94, 133]),
 (134,
  [128,
   129,
   130,
   171,
   100,
   133,
   132,
   143,
   208,
   113,
   118,
   120,
   121,
   122,
   123,
   126]),
 (140,
  [144,
   187,
   132,
   139,
   141,
   142,
   112,
   145,
   146,
   84,
   110,
   120,
   121,
   123,
   190,
   85]),
 (155,
  [160,
   161,
   162,
   165,
   181,
   148,
   149,
   150,
   151,
   152,
   153,
   154,
   156,
   157,
   158,
   159]),
 (170,
  [67,
   169,
   171,
   173,
   174,
   175,
   176,
   177,
   178,
   179,
   148,
   181,
   182,
   183,
   180,
   157]),
 (210,
  [67,
   195,
   229,
   230,
   243,
   206,
   208,
   209,
   242,
   211,
   212,
   213,
   214,
   247,
   218,
   219]),
 (226,
  [225,
   195,
   228,
   229,
   230,
   231,
   232,
   233,
   235,
   237,
   238,
   207,
   241,
   227,
   117,
   239]),
 (346,
  [385,
   386,
   356,
   357,
   358,
   359,
   394,
   371,
   272,
   369,
   339,
   345,
   378,
   347,
   348,
   318]),
 (354,
  [355,
   356,
   357,
   326,
   359,
   363,
   364,
   365,
   272,
   369,
   341,
   345,
   358,
   347,
   348,
   351]),
 (376,
  [384,
   386,
   359,
   328,
   329,
   272,
   369,
   372,
   382,
   377,
   378,
   379,
   380,
   381,
   318,
   383]),
 (379,
  [384,
   386,
   359,
   328,
   329,
   382,
   272,
   341,
   374,
   375,
   376,
   377,
   378,
   380,
   381,
   318]),
 (386,
  [385,
   387,
   389,
   328,
   393,
   395,
   367,
   400,
   335,
   374,
   376,
   345,
   346,
   379,
   378,
   318]),
 (39, [64, 65, 2, 37, 38, 40, 41, 42, 43, 45, 47, 48, 9, 58, 70]),
 (78, [38, 70, 81, 72, 76, 74, 75, 44, 77, 47, 49, 87, 56, 58, 60]),
 (90, [96, 97, 99, 100, 101, 102, 103, 104, 106, 108, 109, 111, 4, 91, 93]),
 (96, [97, 99, 100, 102, 103, 104, 105, 107, 109, 126, 90, 91, 93, 94, 95]),
 (106, [97, 99, 100, 102, 70, 103, 104, 105, 107, 109, 110, 116, 90, 93, 95]),
 (108, [97, 2, 100, 102, 103, 107, 109, 93, 111, 90, 91, 124, 122, 94, 95]),
 (115,
  [132, 177, 136, 73, 171, 146, 112, 113, 114, 183, 57, 95, 188, 190, 127]),
 (128,
  [129, 130, 133, 134, 103, 136, 73, 146, 118, 120, 122, 123, 125, 126, 127]),
 (162,
  [160, 161, 164, 165, 148, 181, 85, 152, 153, 154, 155, 156, 157, 158, 159]),
 (168,
  [144, 66, 132, 133, 167, 143, 112, 113, 50, 51, 117, 120, 122, 187, 190]),
 (201,
  [193, 196, 197, 198, 199, 200, 202, 235, 204, 206, 207, 240, 241, 219, 229]),
 (225,
  [226, 227, 228, 229, 230, 233, 234, 235, 236, 237, 238, 239, 240, 241, 147]),
 (307,
  [304, 323, 292, 325, 263, 297, 272, 305, 306, 308, 309, 310, 265, 312, 319]),
 (308,
  [264, 265, 312, 307, 304, 305, 306, 275, 277, 279, 280, 188, 317, 318, 309]),
 (328,
  [384, 386, 329, 382, 272, 339, 318, 376, 377, 378, 379, 380, 381, 348, 383]),
 (333,
  [363, 327, 361, 330, 331, 332, 334, 335, 272, 338, 340, 373, 344, 372, 350]),
 (355,
  [352, 354, 356, 357, 358, 359, 365, 272, 337, 341, 344, 345, 347, 348, 351]),
 (358,
  [352, 354, 355, 356, 357, 359, 363, 332, 365, 272, 345, 346, 347, 348, 351]),
 (371,
  [384, 353, 388, 327, 393, 366, 272, 369, 402, 403, 407, 346, 348, 378, 318]),
 (9, [3, 5, 6, 39, 8, 10, 11, 12, 13, 14, 15, 16, 19, 26]),
 (11, [32, 48, 5, 6, 8, 9, 10, 12, 13, 14, 15, 16, 23, 26]),
 (70, [2, 71, 72, 73, 74, 39, 78, 61, 87, 88, 57, 47, 106, 63]),
 (75, [44, 74, 76, 77, 78, 47, 81, 50, 19, 55, 56, 95, 94, 63]),
 (81, [80, 69, 74, 75, 76, 77, 78, 48, 88, 82, 83, 119, 56, 87]),
 (85, [160, 161, 162, 100, 71, 40, 76, 167, 140, 141, 84, 150, 153, 158]),
 (88, [70, 71, 105, 42, 43, 142, 89, 144, 81, 86, 87, 121, 91, 95]),
 (99, [96, 97, 123, 103, 104, 105, 106, 107, 109, 110, 90, 91, 93, 94]),
 (150, [160, 161, 164, 85, 148, 149, 151, 152, 153, 154, 155, 156, 158, 159]),
 (163, [192, 161, 194, 198, 193, 202, 199, 206, 176, 244, 215, 120, 247, 191]),
 (172, [171, 167, 169, 203, 173, 177, 175, 112, 113, 50, 149, 215, 58, 233]),
 (205, [195, 196, 197, 198, 199, 200, 202, 204, 206, 207, 209, 51, 219, 239]),
 (208, [67, 227, 134, 243, 242, 209, 210, 211, 212, 181, 214, 215, 218, 213]),
 (209, [227, 196, 211, 242, 202, 205, 208, 210, 243, 212, 213, 247, 250, 252]),
 (214, [224, 161, 193, 171, 206, 207, 208, 210, 117, 215, 217, 218, 188, 125]),
 (218, [161, 195, 229, 199, 171, 208, 210, 147, 245, 214, 215, 217, 219, 221]),
 (309, [324, 293, 264, 306, 304, 305, 274, 307, 308, 278, 312, 314, 188, 285]),
 (329, [384, 359, 328, 382, 366, 340, 341, 376, 377, 378, 379, 380, 381, 318]),
 (339, [356, 359, 328, 367, 272, 340, 341, 342, 343, 344, 345, 346, 349, 350]),
 (347, [354, 355, 356, 357, 358, 359, 364, 365, 366, 272, 345, 346, 348, 351]),
 (351, [352, 354, 355, 356, 357, 358, 359, 332, 365, 272, 344, 345, 347, 348]),
 (357, [352, 354, 355, 356, 358, 359, 364, 332, 272, 345, 346, 347, 348, 351]),
 (374, [386, 388, 389, 359, 335, 403, 399, 373, 375, 408, 345, 379, 380, 381]),
 (377, [384, 328, 329, 382, 272, 341, 375, 376, 378, 379, 380, 381, 318, 383]),
 (380, [384, 359, 328, 329, 382, 374, 375, 376, 377, 378, 379, 381, 318, 383]),
 (13, [35, 8, 9, 10, 11, 12, 14, 15, 16, 49, 18, 23, 26]),
 (19, [5, 38, 9, 42, 75, 76, 77, 14, 16, 17, 18, 20, 74]),
 (38, [19, 100, 37, 39, 40, 74, 109, 78, 45, 72, 51, 42, 95]),
 (58, [132, 39, 42, 171, 172, 78, 144, 113, 50, 56, 57, 124, 190]),
 (101, [97, 100, 102, 103, 105, 109, 110, 113, 90, 91, 93, 94, 95]),
 (130, [128, 129, 132, 134, 112, 118, 120, 121, 122, 124, 125, 126, 127]),
 (142, [147, 166, 138, 139, 140, 146, 141, 50, 51, 84, 88, 121, 143]),
 (147, [192, 161, 225, 105, 235, 142, 144, 146, 117, 215, 218, 222, 95]),
 (151, [160, 161, 165, 204, 177, 148, 149, 150, 183, 152, 154, 155, 157]),
 (159, [160, 161, 162, 164, 148, 150, 152, 153, 154, 155, 156, 157, 158]),
 (182, [164, 169, 170, 173, 174, 176, 177, 179, 148, 117, 206, 183, 181]),
 (190, [51, 132, 166, 167, 168, 140, 112, 242, 115, 228, 58, 187, 188]),
 (192, [161, 194, 163, 193, 259, 202, 147, 212, 213, 247, 217, 252, 191]),
 (193, [192, 194, 163, 198, 199, 201, 202, 176, 244, 214, 312, 154, 191]),
 (216, [288, 257, 258, 195, 260, 197, 262, 264, 265, 240, 259, 281, 261]),
 (247, [192, 194, 163, 233, 235, 204, 209, 210, 244, 248, 250, 252, 287]),
 (305, [288, 304, 293, 263, 272, 306, 307, 308, 309, 310, 312, 284, 325]),
 (327, [368, 326, 369, 265, 330, 331, 332, 333, 366, 272, 337, 338, 371]),
 (361, [353, 356, 230, 360, 362, 363, 332, 333, 334, 335, 367, 348, 330]),
 (384, [389, 328, 329, 371, 318, 376, 377, 378, 379, 380, 381, 382, 383]),
 (8, [48, 3, 4, 9, 10, 11, 12, 13, 14, 15, 16, 23]),
 (67, [66, 68, 211, 74, 76, 77, 208, 210, 51, 181, 170, 42]),
 (107, [96, 99, 102, 103, 136, 106, 108, 109, 110, 104, 93, 94]),
 (184, [164, 169, 171, 173, 174, 175, 176, 177, 178, 180, 181, 183]),
 (187, [181, 51, 167, 168, 140, 112, 113, 243, 117, 186, 190, 245]),
 (211, [67, 227, 202, 215, 242, 208, 209, 210, 243, 212, 213, 183]),
 (212, [192, 161, 243, 171, 242, 208, 209, 210, 211, 244, 213, 231]),
 (242, [230, 243, 208, 209, 210, 211, 212, 213, 244, 221, 190, 245]),
 (330, [331, 326, 327, 361, 363, 332, 333, 334, 338, 372, 373, 349]),
 (332, [356, 357, 358, 327, 361, 330, 331, 333, 334, 336, 373, 351]),
 (353, [356, 230, 359, 360, 361, 362, 363, 367, 368, 371, 340, 318]),
 (381, [384, 328, 329, 318, 374, 376, 377, 378, 379, 380, 382, 383]),
 (399, [389, 393, 407, 397, 335, 400, 402, 403, 404, 374, 375, 408]),
 (14, [16, 19, 6, 23, 8, 9, 10, 11, 12, 13, 15]),
 (47, [50, 51, 75, 78, 70, 39, 24, 73, 55, 28, 46]),
 (56, [112, 113, 144, 74, 58, 81, 57, 42, 75, 125, 78]),
 (66, [68, 161, 146, 51, 100, 72, 152, 36, 74, 168, 67]),
 (72, [122, 2, 51, 74, 70, 38, 71, 73, 42, 66, 78]),
 (73, [128, 72, 115, 70, 71, 24, 42, 87, 44, 122, 47]),
 (166, [190, 164, 149, 255, 120, 137, 207, 188, 141, 142, 174]),
 (213, [192, 208, 210, 211, 212, 243, 230, 209, 202, 219, 242]),
 (270, [271, 294, 277, 261, 230, 292, 268, 235, 188, 221, 269]),
 (278, [273, 274, 195, 276, 277, 264, 275, 309, 315, 286, 303]),
 (306, [272, 304, 307, 308, 309, 310, 305, 312, 324, 321, 320]),
 (331, [272, 350, 228, 230, 326, 327, 330, 332, 333, 334, 341]),
 (334, [338, 340, 230, 326, 360, 361, 330, 331, 332, 333, 362]),
 (365, [272, 354, 355, 340, 358, 359, 345, 347, 348, 356, 351]),
 (382, [384, 376, 341, 377, 328, 329, 378, 379, 380, 381, 318]),
 (10, [16, 23, 8, 9, 26, 11, 12, 13, 14, 15]),
 (43, [37, 54, 105, 88, 41, 42, 39, 44, 45, 93]),
 (48, [80, 49, 50, 51, 37, 81, 39, 7, 11, 8]),
 (77, [19, 76, 67, 81, 41, 42, 75, 44, 74, 78]),
 (84, [112, 144, 100, 85, 71, 40, 87, 140, 142, 95]),
 (131, [132, 117, 93, 121, 122, 123, 124, 126, 110, 127]),
 (194, [192, 193, 163, 244, 219, 247, 200, 207, 204, 191]),
 (221, [242, 230, 249, 217, 218, 235, 220, 268, 270, 223]),
 (234, [240, 225, 229, 231, 232, 235, 236, 237, 238, 239]),
 (243, [208, 209, 210, 211, 212, 213, 249, 187, 242, 223]),
 (363, [353, 354, 358, 359, 360, 361, 330, 362, 333, 367]),
 (385, [272, 400, 386, 391, 389, 375, 345, 346, 359, 394]),
 (404, [400, 408, 387, 389, 407, 405, 410, 335, 403, 399]),
 (5, [16, 1, 3, 6, 19, 7, 9, 11, 12]),
 (32, [50, 51, 41, 25, 26, 11, 44, 30, 31]),
 (64, [112, 113, 51, 69, 54, 55, 39, 110, 65]),
 (76, [19, 81, 67, 59, 85, 74, 75, 77, 78]),
 (180, [176, 178, 179, 181, 183, 184, 169, 170, 206]),
 (223, [224, 240, 243, 228, 51, 233, 171, 221, 237]),
 (224, [240, 228, 230, 214, 171, 156, 237, 174, 223]),
 (252, [192, 209, 244, 245, 247, 249, 250, 257, 256]),
 (280, [321, 308, 293, 294, 279, 281, 284, 297, 317]),
 (304, [288, 305, 306, 307, 308, 309, 325, 312, 287]),
 (325, [304, 305, 307, 324, 310, 312, 315, 317, 319]),
 (344, [367, 368, 402, 339, 341, 343, 355, 333, 351]),
 (352, [355, 356, 357, 358, 359, 345, 348, 364, 351]),
 (375, [400, 385, 399, 389, 374, 377, 379, 380, 335]),
 (387, [400, 386, 404, 389, 345, 378, 395, 410, 335]),
 (408, [400, 401, 404, 389, 374, 407, 367, 396, 399]),
 (2, [1, 50, 70, 6, 39, 40, 72, 108]),
 (6, [1, 2, 5, 7, 9, 11, 12, 14]),
 (23, [16, 17, 8, 10, 11, 12, 13, 14]),
 (28, [52, 41, 42, 27, 44, 29, 30, 47]),
 (36, [16, 33, 34, 35, 51, 44, 12, 66]),
 (40, [2, 51, 52, 37, 38, 39, 84, 85]),
 (45, [51, 38, 39, 41, 42, 43, 44, 74]),
 (54, [64, 53, 55, 41, 42, 43, 74, 46]),
 (55, [64, 75, 53, 54, 41, 74, 47, 63]),
 (63, [33, 75, 70, 55, 59, 60, 61, 62]),
 (141, [144, 51, 85, 166, 120, 139, 140, 142]),
 (143, [144, 146, 51, 142, 134, 168, 50, 126]),
 (167, [112, 149, 85, 168, 187, 172, 126, 190]),
 (245, [242, 230, 232, 218, 187, 252, 250, 255]),
 (248, [195, 244, 197, 198, 247, 233, 237, 277]),
 (249, [256, 257, 243, 294, 250, 252, 221, 302]),
 (250, [209, 257, 245, 247, 249, 252, 237, 229]),
 (255, [179, 244, 245, 166, 199, 232, 265, 222]),
 (268, [288, 258, 292, 261, 271, 269, 270, 221]),
 (277, [195, 276, 286, 278, 308, 248, 260, 270]),
 (315, [273, 318, 261, 278, 316, 317, 286, 325]),
 (319, [272, 320, 322, 307, 228, 325, 321, 317]),
 (321, [272, 320, 306, 228, 280, 265, 322, 319]),
 (326, [354, 372, 373, 327, 265, 330, 331, 334]),
 (338, [272, 336, 337, 327, 330, 333, 334, 335]),
 (362, [353, 230, 359, 360, 361, 363, 334, 335]),
 (369, [272, 354, 371, 356, 327, 376, 346, 359]),
 (372, [400, 340, 341, 326, 376, 330, 333, 373]),
 (373, [272, 400, 372, 374, 326, 330, 332, 333]),
 (383, [384, 376, 328, 377, 378, 380, 381, 318]),
 (403, [402, 371, 404, 389, 374, 407, 406, 399]),
 (407, [367, 403, 404, 389, 406, 408, 371, 399]),
 (3, [16, 4, 5, 8, 9, 42, 12]),
 (7, [48, 51, 37, 22, 6, 21, 5]),
 (15, [16, 8, 9, 10, 11, 13, 14]),
 (33, [16, 34, 35, 36, 37, 69, 63]),
 (60, [65, 78, 42, 59, 61, 62, 63]),
 (116, [129, 100, 87, 136, 121, 106, 138]),
 (136, [128, 51, 50, 115, 116, 118, 107]),
 (145, [146, 137, 104, 121, 138, 139, 140]),
 (191, [192, 193, 194, 163, 51, 215, 217]),
 (217, [192, 244, 214, 215, 218, 221, 191]),
 (222, [147, 132, 198, 244, 219, 188, 255]),
 (286, [273, 275, 276, 277, 278, 315, 188]),
 (302, [336, 370, 294, 311, 249, 295, 303]),
 (317, [308, 325, 279, 280, 315, 316, 319]),
 (336, [272, 338, 230, 367, 332, 302, 335]),
 (342, [339, 340, 341, 343, 349, 350, 335]),
 (343, [339, 340, 341, 342, 344, 228, 350]),
 (349, [368, 339, 340, 341, 342, 330, 367]),
 (350, [339, 340, 341, 342, 343, 331, 333]),
 (364, [352, 354, 357, 359, 345, 347, 348]),
 (393, [386, 371, 389, 378, 395, 402, 399]),
 (17, [16, 18, 19, 20, 23, 12]),
 (26, [32, 9, 10, 11, 12, 13]),
 (35, [16, 33, 34, 51, 36, 13]),
 (57, [115, 51, 70, 56, 41, 58]),
 (62, [37, 42, 59, 60, 61, 63]),
 (86, [91, 87, 88, 89, 74, 103]),
 (111, [112, 100, 103, 90, 108, 109]),
 (138, [144, 145, 146, 116, 137, 142]),
 (185, [178, 179, 181, 169, 173, 174]),
 (275, [273, 274, 308, 278, 301, 286]),
 (324, [272, 306, 292, 309, 283, 325]),
 (360, [353, 230, 361, 362, 363, 334]),
 (366, [371, 356, 327, 329, 347, 367]),
 (368, [353, 341, 327, 344, 348, 349]),
 (402, [371, 405, 344, 393, 403, 399]),
 (1, [2, 51, 50, 6, 5]),
 (27, [41, 28, 29, 30, 44]),
 (30, [32, 25, 27, 28, 29]),
 (49, [48, 51, 13, 78, 37]),
 (59, [76, 60, 61, 62, 63]),
 (61, [59, 60, 70, 62, 63]),
 (65, [64, 51, 60, 37, 39]),
 (69, [64, 33, 44, 80, 81]),
 (80, [48, 81, 68, 69, 79]),
 (114, [112, 113, 146, 115, 95]),
 (251, [232, 254, 179, 253, 219]),
 (273, [315, 274, 275, 286, 278]),
 (274, [265, 275, 309, 278, 273]),
 (279, [280, 308, 300, 317, 295]),
 (310, [312, 305, 306, 307, 325]),
 (337, [355, 359, 338, 335, 327]),
 (406, [401, 403, 407, 405, 367]),
 (4, [8, 90, 3, 12]),
 (18, [17, 19, 20, 13]),
 (20, [17, 18, 19, 12]),
 (24, [25, 71, 73, 47]),
 (29, [44, 27, 28, 30]),
 (52, [40, 41, 51, 28]),
 (89, [88, 103, 86, 87]),
 (137, [144, 145, 138, 166]),
 (139, [145, 140, 141, 142]),
 (271, [268, 188, 269, 270]),
 (303, [288, 302, 278, 311]),
 (320, [321, 306, 322, 319]),
 (323, [312, 291, 195, 307]),
 (388, [345, 371, 374, 367]),
 (394, [345, 346, 391, 385]),
 (395, [393, 386, 387, 335]),
 (397, [400, 405, 398, 399]),
 (405, [402, 404, 397, 406]),
 (410, [400, 387, 404, 389]),
 (25, [24, 32, 30]),
 (34, [33, 35, 36]),
 (46, [50, 54, 47]),
 (68, [80, 66, 67]),
 (83, [81, 82, 87]),
 (253, [179, 254, 251]),
 (254, [179, 253, 251]),
 (269, [268, 270, 271]),
 (276, [286, 277, 278]),
 (290, [272, 289, 261]),
 (316, [315, 317, 318]),
 (322, [320, 321, 319]),
 (391, [345, 394, 385]),
 (401, [400, 408, 406]),
 (21, [22, 7]),
 (22, [21, 7]),
 (31, [32, 50]),
 (53, [54, 55]),
 (82, [81, 83]),
 (92, [41, 44]),
 (189, [188, 132]),
 (220, [221, 215]),
 (246, [240, 132]),
 (256, [249, 252]),
 (289, [290, 301]),
 (311, [302, 303]),
 (392, [389, 367]),
 (396, [408, 367]),
 (409, [400, 389]),
 (79, [80]),
 (98, [91]),
 (119, [81]),
 (135, [132]),
 (186, [187]),
 (203, [172]),
 (313, [235]),
 (370, [302]),
 (390, [389]),
 (398, [397])]

Approach 2: Degree Centrality

The number of other nodes that one node is connected to is a measure of its centrality. NetworkX implements a degree centrality, which is defined as the number of neighbors that a node has normalized to the number of individuals it could be connected to in the entire graph. This is accessed by using nx.degree_centrality(G)





In [5]:



    


nx.degree_centrality(G)



    


















    
Out[5]:








{1: 0.012224938875305624,
 2: 0.019559902200488997,
 3: 0.017114914425427872,
 4: 0.009779951100244499,
 5: 0.022004889975550123,
 6: 0.019559902200488997,
 7: 0.017114914425427872,
 8: 0.029339853300733496,
 9: 0.034229828850855744,
 10: 0.02444987775061125,
 11: 0.034229828850855744,
 12: 0.039119804400977995,
 13: 0.03178484107579462,
 14: 0.02689486552567237,
 15: 0.017114914425427872,
 16: 0.039119804400977995,
 17: 0.014669926650366748,
 18: 0.009779951100244499,
 19: 0.03178484107579462,
 20: 0.009779951100244499,
 21: 0.004889975550122249,
 22: 0.004889975550122249,
 23: 0.019559902200488997,
 24: 0.009779951100244499,
 25: 0.007334963325183374,
 26: 0.014669926650366748,
 27: 0.012224938875305624,
 28: 0.019559902200488997,
 29: 0.009779951100244499,
 30: 0.012224938875305624,
 31: 0.004889975550122249,
 32: 0.022004889975550123,
 33: 0.017114914425427872,
 34: 0.007334963325183374,
 35: 0.014669926650366748,
 36: 0.019559902200488997,
 37: 0.04156479217603912,
 38: 0.03178484107579462,
 39: 0.03667481662591687,
 40: 0.019559902200488997,
 41: 0.04156479217603912,
 42: 0.06356968215158924,
 43: 0.02444987775061125,
 44: 0.044009779951100246,
 45: 0.019559902200488997,
 46: 0.007334963325183374,
 47: 0.02689486552567237,
 48: 0.02444987775061125,
 49: 0.012224938875305624,
 50: 0.08068459657701711,
 51: 0.12224938875305623,
 52: 0.009779951100244499,
 53: 0.004889975550122249,
 54: 0.019559902200488997,
 55: 0.019559902200488997,
 56: 0.02689486552567237,
 57: 0.014669926650366748,
 58: 0.03178484107579462,
 59: 0.012224938875305624,
 60: 0.017114914425427872,
 61: 0.012224938875305624,
 62: 0.014669926650366748,
 63: 0.019559902200488997,
 64: 0.022004889975550123,
 65: 0.012224938875305624,
 66: 0.02689486552567237,
 67: 0.029339853300733496,
 68: 0.007334963325183374,
 69: 0.012224938875305624,
 70: 0.034229828850855744,
 71: 0.039119804400977995,
 72: 0.02689486552567237,
 73: 0.02689486552567237,
 74: 0.05623471882640587,
 75: 0.034229828850855744,
 76: 0.022004889975550123,
 77: 0.02444987775061125,
 78: 0.03667481662591687,
 79: 0.0024449877750611247,
 80: 0.012224938875305624,
 81: 0.034229828850855744,
 82: 0.004889975550122249,
 83: 0.007334963325183374,
 84: 0.02444987775061125,
 85: 0.034229828850855744,
 86: 0.014669926650366748,
 87: 0.0488997555012225,
 88: 0.034229828850855744,
 89: 0.009779951100244499,
 90: 0.03667481662591687,
 91: 0.05134474327628362,
 92: 0.004889975550122249,
 93: 0.05378973105134474,
 94: 0.0488997555012225,
 95: 0.061124694376528114,
 96: 0.03667481662591687,
 97: 0.04156479217603912,
 98: 0.0024449877750611247,
 99: 0.034229828850855744,
 100: 0.07090464547677261,
 101: 0.03178484107579462,
 102: 0.039119804400977995,
 103: 0.06356968215158924,
 104: 0.04156479217603912,
 105: 0.05623471882640587,
 106: 0.03667481662591687,
 107: 0.029339853300733496,
 108: 0.03667481662591687,
 109: 0.05134474327628362,
 110: 0.04645476772616137,
 111: 0.014669926650366748,
 112: 0.06356968215158924,
 113: 0.05623471882640587,
 114: 0.012224938875305624,
 115: 0.03667481662591687,
 116: 0.017114914425427872,
 117: 0.05867970660146699,
 118: 0.05134474327628362,
 119: 0.0024449877750611247,
 120: 0.05378973105134474,
 121: 0.04645476772616137,
 122: 0.07823960880195599,
 123: 0.04645476772616137,
 124: 0.0488997555012225,
 125: 0.05134474327628362,
 126: 0.04645476772616137,
 127: 0.04156479217603912,
 128: 0.03667481662591687,
 129: 0.04156479217603912,
 130: 0.03178484107579462,
 131: 0.02444987775061125,
 132: 0.061124694376528114,
 133: 0.04645476772616137,
 134: 0.039119804400977995,
 135: 0.0024449877750611247,
 136: 0.017114914425427872,
 137: 0.009779951100244499,
 138: 0.014669926650366748,
 139: 0.009779951100244499,
 140: 0.039119804400977995,
 141: 0.019559902200488997,
 142: 0.03178484107579462,
 143: 0.019559902200488997,
 144: 0.0488997555012225,
 145: 0.017114914425427872,
 146: 0.044009779951100246,
 147: 0.03178484107579462,
 148: 0.07579462102689487,
 149: 0.04645476772616137,
 150: 0.034229828850855744,
 151: 0.03178484107579462,
 152: 0.04156479217603912,
 153: 0.04156479217603912,
 154: 0.05623471882640587,
 155: 0.039119804400977995,
 156: 0.05134474327628362,
 157: 0.04156479217603912,
 158: 0.04156479217603912,
 159: 0.03178484107579462,
 160: 0.044009779951100246,
 161: 0.08312958435207823,
 162: 0.03667481662591687,
 163: 0.034229828850855744,
 164: 0.05378973105134474,
 165: 0.05867970660146699,
 166: 0.02689486552567237,
 167: 0.019559902200488997,
 168: 0.03667481662591687,
 169: 0.05378973105134474,
 170: 0.039119804400977995,
 171: 0.06845965770171149,
 172: 0.034229828850855744,
 173: 0.05378973105134474,
 174: 0.05378973105134474,
 175: 0.0488997555012225,
 176: 0.044009779951100246,
 177: 0.05623471882640587,
 178: 0.044009779951100246,
 179: 0.05623471882640587,
 180: 0.022004889975550123,
 181: 0.08068459657701711,
 182: 0.03178484107579462,
 183: 0.05867970660146699,
 184: 0.029339853300733496,
 185: 0.014669926650366748,
 186: 0.0024449877750611247,
 187: 0.029339853300733496,
 188: 0.07334963325183375,
 189: 0.004889975550122249,
 190: 0.03178484107579462,
 191: 0.017114914425427872,
 192: 0.03178484107579462,
 193: 0.03178484107579462,
 194: 0.02444987775061125,
 195: 0.10513447432762836,
 196: 0.05378973105134474,
 197: 0.061124694376528114,
 198: 0.06356968215158924,
 199: 0.06845965770171149,
 200: 0.044009779951100246,
 201: 0.03667481662591687,
 202: 0.05867970660146699,
 203: 0.0024449877750611247,
 204: 0.044009779951100246,
 205: 0.034229828850855744,
 206: 0.05623471882640587,
 207: 0.061124694376528114,
 208: 0.034229828850855744,
 209: 0.034229828850855744,
 210: 0.039119804400977995,
 211: 0.029339853300733496,
 212: 0.029339853300733496,
 213: 0.02689486552567237,
 214: 0.034229828850855744,
 215: 0.04645476772616137,
 216: 0.03178484107579462,
 217: 0.017114914425427872,
 218: 0.034229828850855744,
 219: 0.08312958435207823,
 220: 0.004889975550122249,
 221: 0.02444987775061125,
 222: 0.017114914425427872,
 223: 0.022004889975550123,
 224: 0.022004889975550123,
 225: 0.03667481662591687,
 226: 0.039119804400977995,
 227: 0.05623471882640587,
 228: 0.04156479217603912,
 229: 0.061124694376528114,
 230: 0.06356968215158924,
 231: 0.061124694376528114,
 232: 0.05623471882640587,
 233: 0.05134474327628362,
 234: 0.02444987775061125,
 235: 0.10513447432762836,
 236: 0.04156479217603912,
 237: 0.05867970660146699,
 238: 0.05378973105134474,
 239: 0.05378973105134474,
 240: 0.06601466992665037,
 241: 0.04156479217603912,
 242: 0.029339853300733496,
 243: 0.02444987775061125,
 244: 0.04156479217603912,
 245: 0.019559902200488997,
 246: 0.004889975550122249,
 247: 0.03178484107579462,
 248: 0.019559902200488997,
 249: 0.019559902200488997,
 250: 0.019559902200488997,
 251: 0.012224938875305624,
 252: 0.022004889975550123,
 253: 0.007334963325183374,
 254: 0.007334963325183374,
 255: 0.019559902200488997,
 256: 0.004889975550122249,
 257: 0.06845965770171149,
 258: 0.05867970660146699,
 259: 0.061124694376528114,
 260: 0.061124694376528114,
 261: 0.06601466992665037,
 262: 0.05623471882640587,
 263: 0.05134474327628362,
 264: 0.06845965770171149,
 265: 0.08312958435207823,
 266: 0.04156479217603912,
 267: 0.04156479217603912,
 268: 0.019559902200488997,
 269: 0.007334963325183374,
 270: 0.02689486552567237,
 271: 0.009779951100244499,
 272: 0.11491442542787286,
 273: 0.012224938875305624,
 274: 0.012224938875305624,
 275: 0.014669926650366748,
 276: 0.007334963325183374,
 277: 0.019559902200488997,
 278: 0.02689486552567237,
 279: 0.012224938875305624,
 280: 0.022004889975550123,
 281: 0.05867970660146699,
 282: 0.05867970660146699,
 283: 0.05867970660146699,
 284: 0.05623471882640587,
 285: 0.05134474327628362,
 286: 0.017114914425427872,
 287: 0.06356968215158924,
 288: 0.07579462102689487,
 289: 0.004889975550122249,
 290: 0.007334963325183374,
 291: 0.06356968215158924,
 292: 0.08068459657701711,
 293: 0.06601466992665037,
 294: 0.07579462102689487,
 295: 0.05867970660146699,
 296: 0.06356968215158924,
 297: 0.06601466992665037,
 298: 0.061124694376528114,
 299: 0.07090464547677261,
 300: 0.0488997555012225,
 301: 0.0488997555012225,
 302: 0.017114914425427872,
 303: 0.009779951100244499,
 304: 0.022004889975550123,
 305: 0.03178484107579462,
 306: 0.02689486552567237,
 307: 0.03667481662591687,
 308: 0.03667481662591687,
 309: 0.034229828850855744,
 310: 0.012224938875305624,
 311: 0.004889975550122249,
 312: 0.04156479217603912,
 313: 0.0024449877750611247,
 314: 0.05623471882640587,
 315: 0.019559902200488997,
 316: 0.007334963325183374,
 317: 0.017114914425427872,
 318: 0.05378973105134474,
 319: 0.019559902200488997,
 320: 0.009779951100244499,
 321: 0.019559902200488997,
 322: 0.007334963325183374,
 323: 0.009779951100244499,
 324: 0.014669926650366748,
 325: 0.022004889975550123,
 326: 0.019559902200488997,
 327: 0.03178484107579462,
 328: 0.03667481662591687,
 329: 0.034229828850855744,
 330: 0.029339853300733496,
 331: 0.02689486552567237,
 332: 0.029339853300733496,
 333: 0.03667481662591687,
 334: 0.02689486552567237,
 335: 0.04645476772616137,
 336: 0.017114914425427872,
 337: 0.012224938875305624,
 338: 0.019559902200488997,
 339: 0.034229828850855744,
 340: 0.04156479217603912,
 341: 0.0488997555012225,
 342: 0.017114914425427872,
 343: 0.017114914425427872,
 344: 0.022004889975550123,
 345: 0.061124694376528114,
 346: 0.039119804400977995,
 347: 0.034229828850855744,
 348: 0.04645476772616137,
 349: 0.017114914425427872,
 350: 0.017114914425427872,
 351: 0.034229828850855744,
 352: 0.022004889975550123,
 353: 0.029339853300733496,
 354: 0.039119804400977995,
 355: 0.03667481662591687,
 356: 0.0488997555012225,
 357: 0.034229828850855744,
 358: 0.03667481662591687,
 359: 0.06601466992665037,
 360: 0.014669926650366748,
 361: 0.03178484107579462,
 362: 0.019559902200488997,
 363: 0.02444987775061125,
 364: 0.017114914425427872,
 365: 0.02689486552567237,
 366: 0.014669926650366748,
 367: 0.0488997555012225,
 368: 0.014669926650366748,
 369: 0.019559902200488997,
 370: 0.0024449877750611247,
 371: 0.03667481662591687,
 372: 0.019559902200488997,
 373: 0.019559902200488997,
 374: 0.034229828850855744,
 375: 0.022004889975550123,
 376: 0.039119804400977995,
 377: 0.034229828850855744,
 378: 0.044009779951100246,
 379: 0.039119804400977995,
 380: 0.034229828850855744,
 381: 0.029339853300733496,
 382: 0.02689486552567237,
 383: 0.019559902200488997,
 384: 0.03178484107579462,
 385: 0.02444987775061125,
 386: 0.039119804400977995,
 387: 0.022004889975550123,
 388: 0.009779951100244499,
 389: 0.0488997555012225,
 390: 0.0024449877750611247,
 391: 0.007334963325183374,
 392: 0.004889975550122249,
 393: 0.017114914425427872,
 394: 0.009779951100244499,
 395: 0.009779951100244499,
 396: 0.004889975550122249,
 397: 0.009779951100244499,
 398: 0.0024449877750611247,
 399: 0.029339853300733496,
 400: 0.04156479217603912,
 401: 0.007334963325183374,
 402: 0.014669926650366748,
 403: 0.019559902200488997,
 404: 0.02444987775061125,
 405: 0.009779951100244499,
 406: 0.012224938875305624,
 407: 0.019559902200488997,
 408: 0.022004889975550123,
 409: 0.004889975550122249,
 410: 0.009779951100244499}

If you inspect the dictionary closely, you will find that node 51 is the one that has the highest degree centrality, just as we had measured by counting the number of neighbors.

There are other measures of centrality, namely betweenness centrality, flow centrality and load centrality. You can take a look at their definitions on the NetworkX API docs and their cited references. You can also define your own measures if those don't fit your needs, but that is an advanced topic that won't be dealt with here.

The NetworkX API docs that document the centrality measures are here: http://networkx.readthedocs.io/en/networkx-1.11/reference/algorithms.centrality.html?highlight=centrality#module-networkx.algorithms.centrality

Exercises

The following exercises are designed to get you familiar with the concept of "distribution of metrics" on a graph.

  1. Can you create a histogram of the distribution of degree centralities?
  2. Can you create a histogram of the distribution of number of neighbors?
  3. Can you create a scatterplot of the degree centralities against number of neighbors?
  4. If I have n nodes, then how many possible edges are there in total, assuming self-edges are allowed? What if self-edges are not allowed?

Hint: You may want to use:

plt.hist(list_of_values)

and

plt.scatter(x_values, y_values)

Hint: You can access the dictionary .keys() and .values() and cast them as a list.

If you know the Matplotlib API, feel free to get fancy :).





In [6]:



    


# Possible Answers:
fig = plt.figure(0)
# Get a list of degree centrality scores for all of the nodes.
degree_centralities = list(nx.degree_centrality(G).values())
# Plot the histogram of degree centralities.
plt.hist(degree_centralities)
# Set the plot title. 
plt.title('Degree Centralities')



    


















    
Out[6]:








<matplotlib.text.Text at 0x10fe00a20>










    
























In [7]:



    


fig = plt.figure(1)
neighbors = [len(G.neighbors(node)) for node in G.nodes()]
plt.hist(neighbors)
# plt.yscale('log')
plt.title('Number of Neighbors')



    


















    
Out[7]:








<matplotlib.text.Text at 0x1123cc400>










    
























In [8]:



    


fig = plt.figure(2)
plt.scatter(degree_centralities, neighbors, alpha=0.1)
plt.xlabel('Degree Centralities')
plt.ylabel('Number of Neighbors')



    


















    
Out[8]:








<matplotlib.text.Text at 0x1124c7470>

Exercise

Before we move on to paths in a network, see if you can use the Circos plot to visualize the network.





In [9]:



    


from circos import CircosPlot
import numpy as np

nodes = sorted(G.nodes())
edges = G.edges()
edgeprops = dict(alpha=0.1)
nodecolor = plt.cm.viridis(np.arange(len(nodes)) / len(nodes))  # be sure to use viridis!



    











In [10]:



    


fig = plt.figure(figsize=(6,6))
ax = fig.add_subplot(111)
c = CircosPlot(nodes, edges, radius=10, ax=ax, fig=fig, edgeprops=edgeprops, nodecolor=nodecolor)
c.draw()
plt.savefig('images/sociopatterns.png', dpi=300)

What can you deduce about the structure of the network, based on this visualization?

Nodes are sorted by ID. Nodes are more connected to proximal rather than distal nodes. The data are based on people streaming through an enclosed space, so it makes sense that people are mostly connected to others proximal in order, but occasionally some oddballs stick around.

Paths in a Network

Graph traversal is akin to walking along the graph, node by node, restricted by the edges that connect the nodes. Graph traversal is particularly useful for understanding the local structure (e.g. connectivity, retrieving the exact relationships) of certain portions of the graph and for finding paths that connect two nodes in the network.

Using the synthetic social network, we will figure out how to answer the following questions:

  1. How long will it take for a message to spread through this group of friends? (making some assumptions, of course)
  2. How do we find the shortest path to get from individual A to individual B?

Shortest Path

Let's say we wanted to find the shortest path between two nodes. How would we approach this? One approach is what one would call a breadth-first search (http://en.wikipedia.org/wiki/Breadth-first_search). While not necessarily the fastest, it is the easiest to conceptualize.

The approach is essentially as such:

  1. Begin with a queue of the starting node.
  2. Add the neighbors of that node to the queue.
    1. If destination node is present in the queue, end.
    2. If destination node is not present, proceed.
  3. For each node in the queue:
    1. Remove node from the queue.
    2. Add neighbors of the node to the queue. Check if destination node is present or not.
    3. If destination node is present, end.
    4. If destination node is not present, continue.

Exercise

Try implementing this algorithm in a function called path_exists(node1, node2, G).

The function should take in two nodes, node1 and node2, and the graph G that they belong to, and return a Boolean that indicates whether a path exists between those two nodes or not. For convenience, also print out whether a path exists or not between the two nodes.





In [11]:



    


def path_exists(node1, node2, G):
    """
    This function checks whether a path exists between two nodes (node1, node2) in graph G.
    
    Special thanks to @ghirlekar for suggesting that we keep track of the "visited nodes" to
    prevent infinite loops from happening. 
    
    Reference: https://github.com/ericmjl/Network-Analysis-Made-Simple/issues/3
    """
    visited_nodes = set()
    queue = [node1]
    
    for node in queue:
        neighbors = G.neighbors(node)
        if node2 in neighbors:
            print('Path exists between nodes {0} and {1}'.format(node1, node2))
            return True
            break
        else:
            queue.remove(node)
            visited_nodes.add(node)
            queue.extend([n for n in neighbors if n not in visited_nodes])
        if len(queue) == 0:
            print('Path does not exist between nodes {0} and {1}'.format(node1, node2))
            return False



    











In [12]:



    


# Test your answer below
def test_path_exists():
    assert path_exists(18, 5, G)
    assert path_exists(22, 318, G)
    
test_path_exists()



    


















    






Path exists between nodes 18 and 5
Path exists between nodes 22 and 318

If you write an algorithm that runs breadth-first, the recursion pattern is likely to follow what we have done above. If you do a depth-first search (i.e. DFS), the recursion pattern is likely to look a bit different. Take it as a challenge exercise to figure out how a DFS looks like.

Meanwhile... thankfully, NetworkX has a function for us to use, titled has_path, so we don't have to implement this on our own. :-)

http://networkx.readthedocs.io/en/networkx-1.11/reference/generated/networkx.algorithms.shortest_paths.generic.has_path.html





In [13]:



    


nx.has_path(G, 400, 1)



    


















    
Out[13]:








True

NetworkX also has other shortest path algorithms implemented.

http://networkx.readthedocs.io/en/networkx-1.11/reference/algorithms.shortest_paths.html

We can build upon these to build our own graph query functions. Let's see if we can trace the shortest path from one node to another.

nx.shortest_path(G, source, target) gives us a list of nodes that exist within one of the shortest paths between the two nodes. (Not all paths are guaranteed to be found.)





In [14]:



    


nx.shortest_path(G, 4, 400)



    


















    
Out[14]:








[4, 8, 48, 51, 188, 272, 385, 400]

Incidentally, the node list is in order as well.

Exercise

Write a function that extracts the edges in the shortest path between two nodes and puts them into a new graph, and draws it to the screen. It should also return an error if there is no path between the two nodes.

Hint: You may want to use G.subgraph(iterable_of_nodes) to extract just the nodes and edges of interest from the graph G. You might want to use the following lines of code somewhere:

newG = G.subgraph(nodes_of_interest)
nx.draw(newG)

newG will be comprised of the nodes of interest and the edges that connect them.





In [15]:



    


# Possible Answer:

def extract_path_edges(G, source, target):
    # Check to make sure that a path does exists between source and target.
    if nx.has_path(G, source, target):
        nodes = nx.shortest_path(G, source, target)
        newG = G.subgraph(nodes)
        return newG

    else:
        raise Exception('Path does not exist between nodes {0} and {1}.'.format(source, target))
        
newG = extract_path_edges(G, 4, 400)
nx.draw(newG, with_labels=True)

Challenge Exercise (at home)

These exercises below are designed to let you become more familiar with manipulating and visualizing subsets of a graph's nodes.

Write a function that extracts only node, its neighbors, and the edges between that node and its neighbors as a new graph. Then, draw the new graph to screen.





In [16]:



    


# Possible Answer

def extract_neighbor_edges(G, node):
    neighbors = G.neighbors(node)
    newG = nx.Graph()
    
    for n1, n2 in G.edges():
        if (n1 == node and n2 in neighbors) or (n1 in neighbors and n2 == node):
            newG.add_edge(n1, n2)
            
    return newG

fig = plt.figure(0)
newG = extract_neighbor_edges(G, 19)
nx.draw(newG, with_labels=True)



    


















    
























In [17]:



    


def extract_neighbor_edges2(G, node):
    neighbors = G.neighbors(node)
    newG = nx.Graph()
    
    for neighbor in neighbors:
        if (node, neighbor) in G.edges() or (neighbor, node) in G.edges():
            newG.add_edge(node, neighbor)

    return newG

fig = plt.figure(1)
newG = extract_neighbor_edges2(G, 19)
nx.draw(newG, with_labels=True)

Challenge Exercises (at home)

Let's try some other problems that build on the NetworkX API. Refer to the following for the relevant functions:

http://networkx.readthedocs.io/en/networkx-1.11/reference/algorithms.shortest_paths.html

  1. If we want a message to go from one person to another person, and we assume that the message takes 1 day for the initial step and 1 additional day per step in the transmission chain (i.e. the first step takes 1 day, the second step takes 2 days etc.), how long will the message take to spread from any two given individuals? Write a function to compute this.
  2. What is the distribution of message spread times from person to person? What about chain lengths?




In [18]:



    


# Possible answer to Question 1:
# All we need here is the length of the path.

def compute_transmission_time(G, source, target):
    """
    Fill in code below.
    """
    length = nx.shortest_path_length(G, source, target)
    
    time = sum([i for i in range(1, length+1)])
    
    return time

compute_transmission_time(G, 14, 4)



    


















    
Out[18]:








3

















In [19]:



    


# Possible answer to Question 2:
# We need to know the length of every single shortest path between every pair of nodes.
# If we don't put a source and target into the nx.shortest_path_length(G) function call, then
# we get a dictionary of dictionaries, where all source-->target-->lengths are shown.

lengths = []
times = []
for source, sink_length in nx.shortest_path_length(G).items():
    for sink, length in sink_length.items():
        times.append(sum(range(1, length+1)))
        lengths.append(length)
        
plt.figure(0)
plt.bar(Counter(lengths).keys(), Counter(lengths).values())

plt.figure(1)
plt.bar(Counter(times).keys(), Counter(times).values())



    


















    
Out[19]:








<Container object of 10 artists>

Hubs Revisited

It looks like individual 19 is an important person of some sorts - if a message has to be passed through the network in the shortest time possible, then usually it'll go through person 19. Such a person has a high betweenness centrality. This is implemented as one of NetworkX's centrality algorithms. Check out the Wikipedia page for a further description.

http://en.wikipedia.org/wiki/Betweenness_centrality





In [20]:



    


btws = nx.betweenness_centrality(G, normalized=False)
plt.bar(btws.keys(), btws.values())



    


















    
Out[20]:








<Container object of 410 artists>

Exercise

Plot betweeness centrality against degree centrality for the network data.





In [21]:



    


# Possible answer:

deg_centrality = nx.degree_centrality(G)
btw_centrality = nx.betweenness_centrality(G)

deg_cent_sorted = [i[1] for i in sorted(zip(deg_centrality.keys(), deg_centrality.values()))]
btw_cent_sorted = [i[1] for i in sorted(zip(btw_centrality.keys(), btw_centrality.values()))]

plt.scatter(deg_cent_sorted, btw_cent_sorted)
plt.xlabel('degree')
plt.ylabel('betweeness')
plt.title('centrality scatterplot')



    


















    
Out[21]:








<matplotlib.text.Text at 0x1166d4860>

Think about it...

From the scatter plot, we can see that the dots don't all fall on the same line. Degree centrality and betweenness centrality don't necessarily correlate. Can you think of scenarios where this is true?

What would be the degree centrality and betweenness centrality of the middle connecting node in the barbell graph below?





In [22]:



    


nx.draw(nx.barbell_graph(5, 1))



    


















    
























In [ ]:

Content source: SubhankarGhosh/NetworkX

Similar notebooks:

notebook.community | gallery | about